package william.heap;

import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

/**
 * @author ZhangShenao
 * @date 2024/2/26
 * @description <a href="https://leetcode.cn/problems/top-k-frequent-elements/description/">...</a>
 */
public class Leetcode347_前K个高频元素 {
    /**
     * 借助堆排序实现
     * 首先使用HashMap建立一个词频表
     * 然后创建一个容量为k的小根堆,堆中元素为数字,比较方式为数字出现的频率
     * 遍历词频表中的数字,将数字进行入堆处理:
     * 如果堆中元素小于k个,则直接入堆
     * 如果当前数字的词频 > 堆顶元素的词频,则将堆顶元素弹出,并将该数字压入堆中
     * 如果当前数字的词频 < 堆顶元素的词频,则直接丢弃当前数字
     * 最后返回堆中的数字
     * <p>
     * 时间复杂度O(N*logK) 遍历数组O(N) x k个元素的堆操作
     * 空间复杂度O(N) 长度为N的词频表+长度为k的堆
     */
    public int[] topKFrequent(int[] nums, int k) {
        //边界条件校验
        if (nums == null || nums.length < k) {
            return new int[0];
        }

        //利用HashMap维护一个词频表,key=数组中的数字 value=数字出现的频率
        HashMap<Integer, Integer> frequency = new HashMap<>(nums.length);
        for (int n : nums) {
            frequency.put(n, frequency.getOrDefault(n, 0) + 1);
        }

        //创建一个长度为k的小根堆,堆中的元素为数组中的数字,比较方式为数字出现的频率
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(Comparator.comparingInt(frequency::get));

        //遍历词频表中的元素,进行入堆操作
        for (Map.Entry<Integer, Integer> f : frequency.entrySet()) {
            int key = f.getKey();
            int val = f.getValue();
            if (minHeap.size() < k) {    //堆中元素不足k个,直接将当前元素入堆
                minHeap.offer(key);
                continue;
            }

            if (val < frequency.get(minHeap.peek())) {   //当前元素出现的频率<堆顶元素,直接跳过
                continue;
            }

            //当前元素出现的频率>堆顶元素,将堆顶元素弹出,并将当前元素入堆
            minHeap.poll();
            minHeap.offer(key);
        }

        //返回堆中的k个元素
        int[] result = new int[k];
        for (int i = 0; i < k; i++) {
            result[i] = minHeap.poll();
        }
        return result;
    }
}
